We consider the complexity of equivalence and learning for multiplicity treeautomata, i.e., weighted tree automata over a field. We first show that theequivalence problem is logspace equivalent to polynomial identity testing, thecomplexity of which is a longstanding open problem. Secondly, we derive lowerbounds on the number of queries needed to learn multiplicity tree automata inAngluin's exact learning model, over both arbitrary and fixed fields. Habrard and Oncina (2006) give an exact learning algorithm for multiplicitytree automata, in which the number of queries is proportional to the size ofthe target automaton and the size of a largest counterexample, represented as atree, that is returned by the Teacher. However, the smallesttree-counterexample may be exponential in the size of the target automaton.Thus the above algorithm does not run in time polynomial in the size of thetarget automaton, and has query complexity exponential in the lower bound. Assuming a Teacher that returns minimal DAG representations ofcounterexamples, we give a new exact learning algorithm whose query complexityis quadratic in the target automaton size, almost matching the lower bound, andimproving the best previously-known algorithm by an exponential factor.
展开▼
